package letcode.oneQuestionPerDay._202004._09;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description: 括号生成
 * @Date: 2020/4/9
 * @Author: 许群星
 */
public class BracketGenerating_2 {
    public static void main(String[] args) {
        int a=5;
        int b=3;
        List<String> list=generateParenthesis(b);
//        System.out.println(list.size());
        for (String s:list
             ) {
            System.out.println(s);
        }
    }
    //提供方法     换种方法 直接取有效的   递归问题    ~通过~
    //fn=f1+fn-1=f2+fn-2=f3+fn-3=fn-1+f1
    public static List<String> generateParenthesis(int n) {
        List<String> ans=new ArrayList<>();
        if (n==1){
            String temp="()";
            ans.add(temp);
            return ans;
        }
        //fn
        List<String> strN=generateParenthesis(n-1);
        for (String s:strN
             ) {
            ans.add("("+s+")");
        }
        //f1+fn-1=f2+fn-2=f3+fn-3=fn-1+f1
        for (int i = 1; i <n ; i++) {
            List<String> list1=generateParenthesis(i);
            List<String> list2=generateParenthesis(n-i);
            for (String s1:list1
                 ) {
                for (String s2:list2
                     ) {
                    if (!ans.contains(s1+s2))
                        ans.add(s1+s2);
                }
            }
        }
        return ans;
    }

}
/*
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */